package 贪心算法;

public class 分发糖果 {
    static class Solution{
        public int candy(int[] ratings){
            int[] candyVec = new int[ratings.length];
            candyVec[0] = 1;
            //从前往后遍历  判断右比左大
            for (int i = 1; i < candyVec.length; i++) {
                if (ratings[i]>ratings[i-1]){
                    candyVec[i] += candyVec[i-1]+1;
                }else {
                    candyVec[i]=1;
                }
            }
            //再从后往前遍历 判断左比右大
            for (int i = candyVec.length-2; i >= 0; i--) {
                if (ratings[i]>ratings[i+1]){
                    candyVec[i] = Math.max(candyVec[i+1]+1,candyVec[i]);
                }
            }
            int ans = 0;
            for (int s :
                    candyVec) {
                ans += s;
            }
            return ans;
        }
    }

}
